Turbo coding represents a particularly powerful channel-coding method for the transmission of digital data via a mobile radio transmission channel. So-called turbo codes are used for turbo coding. Turbo codes are binary recursive convolution codes, which are linked in parallel. Turbo coding is used in particular for third-generation mobile radio systems based on UMTS-3GPP Standard (UMTS: Universal Mobile Telecommunication System; 3GPP: 3rd Generation Partnership Project.
FIG. 1 illustrates a turbo coder based on the UMTS-3GPP Standard, which comprises two recursive systematic convolution coders 1 and 2, which are also referred to as RSC coders (RSC—recursive systematic convolutional). In this case, the systematic output of the second RSC coder 2 which loops through the input signal of the RSC coder 2 is not used, and is therefore not shown. The first RSC coder 1 receives the input bit sequence xs(k) directly, while an interleaver 3 is connected upstream on the input side of the second RSC coder 2 and carries out block-by-block interleaving of the input bit sequence xs(k). Each RSC coder 1 and 2 uses a shift register with feedback to generate redundant information items xp1(k) and xp2(k), respectively. The resultant coded data sequence is produced by linking two code components, with the first code component comprising the systematic information xs(k) and the redundant information xp1(k) of the first RSC coder 1, and the second code component comprises the redundant information xp2(k) of the second RSC coder 2. The code components are linked by means of a multiplexer (not illustrated) which assembles the individual bit streams xs(k), xp1(k) and xp2(k) in a suitable manner to form a resultant data sequence. A puncturer (which is not illustrated) which masks out part of the redundant information xp1(k) and xp2(k) in the coded data sequence is in general provided in order to produce a higher code rate Rc than ⅓, for example a code rate of Rc=½, that is to say two bits of the coded data sequence are associated with one bit of the input sequence xs(k).
FIG. 2 illustrates a turbo decoder which is used at the mobile radio receiver. In a similar manner to the turbo coder illustrated in FIG. 1, the turbo decoder uses two decoder elements 4 and 5 in order to process the two code components. These are so-called soft-in-soft-out decoders, which are also referred to as SISO decoders. The input and output signals of SISO decoders such as these are not binary-decision signals, but are digital signals with an appropriate amplitude resolution. SISO decoders typically operate using the MAP algorithm (maximum a-posteriori) or the SOVA (Soft Output Viterbi Algorithm). The input and output variables are, in particular, variables based on a LLR representation (LLR: Log-Likelihood Ratio). An LLR variable is a probability statement and is defined as the logarithm of the ratio between the probability of a logic 0 and the probability of a logic 1 (alternatively, the LLR variable is frequently also defined as the logarithm of the ratio between the probability of a logic 1 and the probability of a logic 0). LLR values with positive mathematical signs make it possible to deduce the presence of a logic 0, while LLR values with negative mathematical signs indicate the presence of a logic 1. The magnitude of the LLR value in this case indicates the reliability of the hypothesis of a logic 1 or a logic 0. The greater the magnitude of the LLR value, the more reliable is the hypothesis of a logic 1 or a logic 0.
The turbo decoder receives three sequences Ls(k), Lp1(k) and Lp2(k) of LLR values which correspond to the transmitted sequence elements xs(k), xp1(k) and Xp2(k). The bits xs(k) and the sequence Ls(k) are also respectively referred to as systematic bits and systematic LLR values or systematic information. Based on the received LLR sequences Ls(k) and Lp1(k) or Lp2(k) and on the a-priori LLR values La1(k) and La2(k) respectively, generated during the final decoding element, each of the decoder elements 4 and 5 produces two output signals, specifically LLR values Lo1(k) and Lo2(k), respectively, of so-called a-posteriori information and LLR values Le1(k) and Le2(k), respectively, of so-called extrinsic information. The a-posteriori LLR values Lo1(k) and Lo2(k) in this case respectively correspond to the uncoded data sequence xs(k) (see FIG. 1), in which case the mathematical sign of the a-posteriori values Lo1(k) or Lo2(k) is used to deduce the binary data sequence xs(k). This procedure is also described by the expression hard decision. The a-posteriori LLR values Lo1(k) and Lo2(k) are referred to as soft output values of the respective decoder element 4 or 5. The extrinsic information Le1(k) or Le2(k) respectively, is additional information obtained during the respective decoding element, and is used as a-priori information La2(k) and La1(k), respectively, during the subsequent decoding element. Furthermore, the respective extrinsic information Le1(k) and Le2(k) describes the convergence of the decoding process.
The following relationship applies to the a-posteriori information Lo1(k) and Lo2(k), respectively:Lo1(k)=Ls(k)+La1(k)+Le1(k)  (Equation 1)Lo2(k)=Ls(k)+La2(k)+Le2(k)  (Equation 2).
Since an interleaver 3 (see FIG. 1) is provided in the turbo coder, two deinterleavers 6 and 7 as well as two interleavers 8 and 9 are used in the turbo decoding process.
The turbo decoding is carried out iteratively. In this case, the extrinsic values Le2(k) of the decoder element 5 during the iteration i are fed back to the SISO decoder element 4 as a-priori values La1(k) for the iteration i+1. At the start of the decoding process, the a-priori values La1 (k) are set to 0, since there is an equal probability of the transmission of a logic 0 or a logic 1. During the last iteration, the a-posteriori values Lo2(k) of the second decoder element 5 are introduced by means of the deinterleaver 7 into the originally transmitted bit sequence, resulting in the LLR values L′o2(k). A hard decision based on these values L′o2(k) results in the uncoded transmission-end data sequence xs(k) (see FIG. 1).
FIG. 3 shows an alternative refinement of a turbo decoder. Blocks and signals which are provided with the same reference symbols in FIG. 2 and FIG. 3 correspond to one another. In this embodiment, the second decoder element 5′ has no input for reception of the systematic LLR values Ls(k). In this situation, the a-priori information La2(k) of the second decoder element 5′ is obtained from the sum of the extrinsic information Le1(k) of the first decoder element 4 and the systematic information Ls(k). In contrast to this, the a-priori information La1(k) of the first decoder element 4 corresponds to the extrinsic information Le2(k) of the second decoder element 5′. This refinement also makes use of the fact that the sum Le1(k)+Ls(k) is equivalent to the difference Lo1(k)−La1(k) and the variable Le2(k) is equivalent to the difference Lo2(k)−La2(k). It is also possible to provide in an analogous manner (not illustrated) for the first decoder element rather than the second decoder element not to have an input for reception of the systematic LLR values Ls(k), in which case the a-priori information La1(k) of the first decoder element is obtained from the sum of the extrinsic information Le2(k) of the second decoder element and the systematic information Ls(k).
Provided that the decoding process has not yet converged, the reliability of the a-posteriori information Lo1(k) and Lo2(k) typically increases in each iteration, that is to say the magnitude of the LLR values Lo1(k) and Lo2(k) becomes greater If the decoding process has already converged, further iterations, for example when using a fixed predetermined number of iterations for decoding, result only in additional computation effort and thus additional wastage of performance without increasing the reliability of the decoding. In a decoding method which operates particularly efficiently, the number of iterations should thus be adaptively matched to the reception conditions.
A large number of different termination conditions are known from the prior art for adaptive matching of the number of iterations. These termination conditions are in this case based on the checking of the information obtained during the decoding process, that is to say typically on the a-posteriori information Lo1(k) or Lo2(k), respectively, the extrinsic information Le1(k) or Le2(k), respectively, or the a-priori information La1(k) or La2(k), respectively, with these information items also being referred to as decoding parameters.
The termination criteria which are known from the prior art can be subdivided into two types:                a) so-called hard-decision-based termination criteria, and        b) so-called soft-decision-based termination criteria.Furthermore, the termination criteria from the prior art as described in the following text differ in that these can either only identify that the decoding process has converged or else they can additionally confirm that the decoding process is diverging, that is to say it is not possible to decode the received block within a predetermined number of iterations.        
In the following text, the variables Loi(k), Lei(k) and Lai(k) denote the LLR values of the a-posteriori information, of the extrinsic information and of the a-priori information, respectively, for the half-iteration i. In this case, a half-iteration corresponds to one decoding element.
The decision variables for the hard-decision-based termination criteria are obtained as a function of binary-decision bits in the decoding parameters.
One typical representative of the hard-decision-based termination criteria is the so-called HDA criterion (HDA—hard decision aided), which is described in the document “Two Simple Stopping Criteria for Turbo Decoding”, R. Y. Shao et al., IEEE Transactions on Communications, Vol. 67, No. 8, August 1999, pages 1117 to 1120. The HDA criterion is based on the evaluation of the binary-decision bit sequence of the a-posteriori information Loi(k). The turbo decoding is terminated when:sgn(Loi(k))=sgn(Loi−1(k))∀kε(1 . . . K)  (Equation 3).In this case, the variable K describes the number of systematic bits in the data block. The turbo decoding is thus terminated when all of the binary-decision bits of the a-priori information Loi(k) in the half-iteration i match all of the binary-decision bits of the a-priori information Loi−1(k) from the previous half-iteration i−1. Alternatively, the binary-decision bits of the a-posteriori information of a decoder element 4 or 5 can also be compared from two successive (complete) iterations.
A further hard-decision-based termination criterion is represented by the so-called GHDA criterion (GHDA—generalized hard decision aided). The GHDA criterion is a generalization of the HDA criterion. The GHDA criterion is described in the document “Generalised stopping criterion for iterative decoders”, Electronic Letters, Vol. 39, No. 13, June 2003, pages 993 and 994. The GHDA criterion is based on the determination of the number of mathematical sign discrepancies between the LLR values Loi(k) and Loi−1(k) of the a-posteriori information for two successive half-iterations (or alternatively for two successive iterations) for the entire data block. The turbo decoding process is then interrupted when the number of mathematical sign discrepancies is less than or equal to a first threshold value θ1. In this case, the turbo decoding process is already converging sufficiently. Furthermore, the turbo decoding process is terminated when the number of mathematical sign discrepancies is greater than or equal to a second threshold value θ2, in which case the second threshold value θ2 is greater than the first threshold value 01. Compliance with this second termination condition indicates that the turbo decoding process is diverging, that is to say reliable decoding of the received data block is not possible within a predetermined number of iterations. This allows a block decoding process which promises to be unsuccessful to be terminated at an early stage during the decoding process.
On the other hand, the GHDA criterion has the disadvantage that the decision bits of the a-posteriori information Loi−1(k) of the last half-iteration i−1 (or alternatively the last iteration) must be temporarily stored for the mathematical sign comparison. A memory with a memory size of K bits is required for temporary storage, where K corresponds to the number of systematic bits in a data block.
A further hard-decision-based termination criterion, specifically the so-called SDR criterion (SDR—sign difference ratio) is described in the document “A Simple Stopping Criterion for Turbo Decoding”, Y. Wu et al., IEEE Communications Letters, Vol. 4, No. 8, August 2000, pages 258 to 260. The SDR criterion is used to define a decision function which indicates the number of mathematical sign discrepancies between the values Lai(k) of the a-priori information and the values Lei(k) of the extrinsic information in each half-iteration (or alternatively in each iteration). The turbo decoding process is terminated if the value of the decision function Ei for a half-iteration i (or alternatively for an iteration i) is less than or equal to a predefined threshold value 0. The decision function Ei may be indicated in the following form:
                              E          i                =                                            1              K                        ⁢                                          ∑                                  k                  =                  1                                K                            ⁢                                                                    f                    i                                    ⁡                                      (                    k                    )                                                  ⁢                                                                  ⁢                where                ⁢                                                                  ⁢                                                      f                    i                                    ⁡                                      (                    k                    )                                                                                =                      {                                                                                0                                                        if                                                                                                      sgn                        ⁡                                                  (                                                                                    L                              a                              i                                                        ⁡                                                          (                              k                              )                                                                                )                                                                    =                                              sgn                        ⁡                                                  (                                                                                    L                              e                              i                                                        ⁡                                                          (                              k                              )                                                                                )                                                                                                                                                          1                                                        if                                                                                                      sgn                        ⁡                                                  (                                                                                    L                              a                              i                                                        ⁡                                                          (                              k                              )                                                                                )                                                                    ≠                                              sgn                        ⁡                                                  (                                                                                    L                              e                              i                                                        ⁡                                                          (                              k                              )                                                                                )                                                                                                                                .                                                          (                  Equation          ⁢                                          ⁢          4                )            
A further half-decision-based termination criterion which is based on carrying out a cyclic redundancy check (CRC) is known from the document “Reducing Average Number of Turbo Decoding Iterations”, Electronic Letters, Vol. 35, No. 9, April 1999, pages 701 and 702. A CRC checking pattern (parity bits) is in each case attached to the uncoded payload data, which is obtained as the division remainder from a polynomial division of the payload data polynomial by a generator polynomial. During a CRC, a check is carried out in the receiver to determine whether the received payload data and the received CRC checking pattern match one another. In the case of the CRC termination criterion, a CRC is carried out with respect to the turbo-decoded signal, that is to say with respect to the binary-decision bit sequence of the a-posteriori information Loi(k). In this case, the CRC can be carried out during each iteration. The turbo decoding process is terminated when using this termination criterion when the CRC is correct. The probability of incorrect termination depends on the length of the generator polynomial. In this case, the probability decreases as the length of the generator polynomial increases.
In the case of soft-decision-based termination criteria, a metric relating to non-binary-decision decoding parameters is compared with a predefined threshold value.
One example of a soft-decision-based termination criterion is represented by the so-called sum criterion (SUM criterion), which is described in the document “Low Complexity Stopping Criteria for UMTS Turbo-Decoders”, F. Gilbert et al., Vehicular Technology Conference, Vol. 4, April 2003, pages 2376 to 2380. In the case of this criterion, the sum Si of the magnitudes of the a-posteriori information is determined after each half-iteration i (or alternatively after each iteration) using the following equation:
                              S          i                =                              ∑                          k              =              1                        K                    ⁢                                                                                    L                  o                  i                                ⁡                                  (                  k                  )                                                                    .                                              (                  Equation          ⁢                                          ⁢          5                )            The turbo decoding process is terminated if the following relationship is satisfied:Si−Si−1≦0.  (Equation 6).In this case, the presence of the condition in accordance with Equation 6 indicates, inter alia, that the decoding process is diverging, that is to say the respective data block cannot be decoded within a maximum number of iterations.
A further representative of a soft-decision-based termination criterion is the so-called minimum criterion (MIN criterion), which is described in the documents “Decoding Metrics and their Application in VLSI Turbo Decoders”, Z. Wang et al., Proc. 2000 Conference on Acoustics, Speech, and Signal Processing (ICASSP 00), September 2000, pages 3370 to 3373, and “Stopping Rules for Turbo Decoders”, A. Matache et al., TMO Progress Report 42-142, August 2000, http:///tda.jpl.nasa.gov/progress report/, Jet Propulsion Laboratory, Pasadena. In this case, the minimum of the magnitude of the soft output values Loi(k) is determined after each half-iteration i (or alternatively after each iteration) using the following calculation rule:δi=min|Loi(k)  (Equation 7).1≦k≦KThe turbo decoding process is terminated when δi is greater than a predefined threshold value θ.
It is also known from the document that has already been cited above “Low Complexity Stopping Criteria for UMTS Turbo-Decoders” for the SUM criterion and the MIN criterion to be combined as a SUM-MIN criterion. The turbo decoding process is terminated as soon as one of the two individual criteria is satisfied. In this case, the SUM-MIN criterion uses not only the capability of the SUM criterion to identify the divergence of the decoding process, but also the capability of the MIN criterion to confirm the convergence of the decoding process.
During extensive comparative simulations using different values for the signal-to-noise ratio, it was found that, when using the GHDA criterion, the mean number of iterations of a turbo decoding process actually carried out is at its lowest in comparison to other termination criteria from the prior art, on average, in particular for low values of the signal-to-noise ratio. This means that the use of the GHDA criterion minimizes the computation effort and thus also the power consumption for turbo decoding. As already stated above, however, an additional buffer store with a size of K bits is required to hold the decision bits from the last half-iteration (or iteration) when using the GHDA criterion.